
/**
 * @file	queue.h
 * @author  Alessandro Carrega <contact@alexcarrega.com>
 * @version 2.0
 * 
 * \class Queue
 *
 * \ingroup GraphMaxFlow
 *
 * \brief Coda con elementi di tipo intero e dimensione fissa.
 * 
 * @secion LICENSE
 *
 * This file is part of graph_max_flow.
 *
 * graph_max_flow is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * graph_max_flow is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with graph_max_flow.  If not, see <http://www.gnu.org/licenses/>.
 * 
 * @section DESCRIPTION
 *
 * Versione ottimizzata per velocizzare il calcolo del percorso
 * tra due nodi in un grafo.
 * Con questa coda i valori interi che rappresentano i nodi
 * presentano tre diversi stati possibili:
 *
 * TO_VISIT: nodo da visitare, non ancora inserito in coda;
 * IN_QUEUE: nodo da vistare, presente in coda;
 * VISITED: nodo visitato, estratto precedentemente dalla coda.
 *
 * Esempio:
 * il nodo 5 è ancora da visitare, quindi ha uno stato TO_VISIT.
 * Inserisco il nodo 5 nella coda, ora lo stato è IN_QUEUE (ancora da visitare).
 * Estraggo dalla coda il nodo 5, ora lo stato è VISITED.
 */

#ifndef QUEUE_H
#define QUEUE_H

#include <stdint.h>

class Queue {

	/**
	 * Indica lo stato dei nodi
	 */
	enum NODE_TYPE {
		TO_VISIT = 0, /**< nodo da visitare, MAI stato in coda. */
		IN_QUEUE = 1, /**< nodo da visitare, PRESENTE in coda */
		VISITED = 2 /**< nodo visitato, NON PRESENTE in coda */
	};

public:
	/**
	 * \brief Nuova Coda di dimensione finita pari al numero di nodi.
	 * \param[in] num_node numero dei nodi del grafo
	 */
	Queue(int num_node);
	/**
	 * \brief Indiica se la coda è vuota.
	 * \return TRUE se la code è vuota, altrimenti FALSE
	 */
	bool empty();
	/// Svuota la code e azzerta le visite dei nodi.
	void reset();
	/**
	 * \brief Inserisce un nuovo nodo nella coda.
	 * \param[in] u nodo da inserire nella coda
	 * 
	 * Lo stato del nodo cambia in Queue::IN_QUEUE.
	 * a prescindere dallo stato del nodo.
	 * 
	 */
	void enqueue(int u);
	/**
	 * \brief Estrae un nodo dalla coda.
	 * \return Il nodo estratto.
	 * 
	 * Lo stato del nodo cambia in Queue::VISITED
	 * a prescindere dallo stato del nodo.
	 */
	int dequeue();
	/**
	 * \brief Indica se il nodo è nello stato Queue::TO_VISIT.
	 * \param[in] u nodo 
	 * \return TRUE se il nodo è nello stato Queue::TO_VISIT, altrimenti FALSE
	 */
	bool is_to_visit(int u);
	/**
	 * \brief Indica se il nodo è nello stato Queue::IN_QUEUE.
	 * \param[in] u nodo 
	 * \return TRUE se il nodo è nello stato Queue::IN_QUEUE, altrimenti FALSE
	 */
	bool is_in_queue(int u);
	/**
	 * \brief Indica se il nodo è nello stato Queue::VISITED.
	 * \param[in] u nodo 
	 * \return TRUE se il nodo è nello stato Queue::VISITED, altrimenti FALSE
	 */
	bool is_visited(int u);

private:
	int *q_; ///< vettore allocato nel costruttore con num_node elementi.
	int head_, ///< indice delle testa della coda  
		tail_; ///< indice della fine della coda
	int num_node_; ///< numero di nodi, dimensione fissa della coda
	/**
	 * Indica lo stato del nodo, Il nodo è l'indice del vettore.
	 * \par Esempio:
	 * \code visited_[u] \endcode contiene lo stato del nodo \p u
	 * (Queue::TO_VISIT, Queue::IN_QUEUE o Queue::VISITED).
	 */
	uint8_t *visited_; 
};

#endif // QUEUE_H
